package com.wrial.kind.linkedList;
/*
 * @Author  Wrial
 * @Date Created in 21:22 2020/8/7
 * @Description
 * 输入: 1->2->2->1
 * 输出: true
 */

public class IsPalindrome {
    /**
     * 将它复制到数组中去，然后使用双指针
     * 或者使用快慢指针找到中点，然后对前半部分逆序，逐个对比
     * 如果是奇数情况，链表变化如下
     *
     * 1.对后半部分逆转
     * 1   2   3   2   1
     *       slow
     *
     * 3 -> null     slow.next = newHead(前半部分的2的next也是3，因此到最后会交叉)
     * newHead
     *
     * 2 -> 3 -> 1
     * 1(newHead) -> 2 ->3
     *
     * 现在的结构如下
     * 1  2
     *       3
     * 1  2
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next ==null) return true;
        ListNode fast = head.next, slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //说明是偶数个  slow需要往后移动才能匹配
        if (fast != null) {
            slow = slow.next;
        }

        ListNode newHead = null;

        while (slow != null) {
            ListNode nextSlow = slow.next;
            slow.next = newHead; //将slow串在newHead前面
            newHead = slow; //更新newHead
            slow = nextSlow;
        }
        while (newHead!=null&&head!=null){

            if (newHead.val!=head.val){
                return false;
            }
            System.out.println(head.val);
            newHead = newHead.next;
            head = head.next;
        }
        return true;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
